package leetcode.tree_problem;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 94. 二叉树的中序遍历【迭代】
 * https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
 */
public class InorderTraversalFunTwo {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null){
           return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
                //这里很巧妙画图好理解
            }
            //很巧妙这个循环走完，因为是先入了栈才移动cur所以while走完时栈的顶端就是最左节点
            cur = stack.pop();
            list.add(cur.val);
            //左中右此时上面已经处理完了左并且将中加入了list此时只需要处理右即让操作节点cur移到right；但是right第一次时空
            //妙的就在这里此时栈顶已经出过一次了所以此时是第二个最左节点画个图就秒懂了
            cur = cur.right;

            /**
             * 下面这个错误就很有意思，while走完栈顶已经在最左节点
             */
//            if (cur.right != null){
//                stack.push(cur.right);
//            }
        }
        return list;
    }
}
